package week_ten;

import java.util.ArrayList;
import java.util.List;

public class FallingSquares_699 {
    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> currHeight = new ArrayList<>();//存放当前方块的高度
        List<Integer> maxlist = new ArrayList<>();//存放当前最大高度
        if (positions == null || positions.length == 0) {
            return maxlist;
        }
        int maxH = positions[0][1];
        int high = positions[0][1];
        currHeight.add(high);
        maxlist.add(maxH);
        for (int i = 1; i < positions.length; i++) {
            high = positions[i][1];
            //判断当前方块能否放在之前的方块上方，并取得最高值
            for (int j = i - 1; j >= 0; j--) {
                if (!(positions[j][0] >= positions[i][0] + positions[i][1] || positions[j][0] + positions[j][1] <= positions[i][0])) {
                    int temp = currHeight.get(j) + positions[i][1];
                    if (temp > high) {
                        high = temp;
                    }
                }
            }
            currHeight.add(high);
            if (high > maxH) {
                maxH = high;
            }
            maxlist.add(maxH);
        }
        return maxlist;
    }
}
